package com.yoshino.leetcode.interview150.list;

import java.util.*;

public class LRUCache {
    DList dList;
    Map<Integer, Node2> map;
    int capacity;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        dList = new DList();
    }
    
    public int get(int key) {
        Node2 node2 = map.get(key);
        if (node2 == null) {
            return -1;
        }
        if (!dList.isFirst(node2)) {
            dList.moveFirst(node2);
        }
        return node2.value;
    }
    
    public void put(int key, int value) {
        Node2 node = map.get(key);
        if (node != null) {
            node.value = value;
            if (!dList.isFirst(node)) {
                dList.moveFirst(node);
            }
        } else {
            Node2 node2 = new Node2(key, value);
            if (dList.getSize() == capacity) {
                Node2 tail = dList.removeTail();
                map.remove(tail.key);
            }
            dList.addFirst(node2);
            map.put(key, node2);
        }
    }
}

class Node2 {
    int key, value;
    Node2 next, pre;

    public Node2() {
    }

    public Node2(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class DList {
    private int size;
    private Node2 head = new Node2();
    private Node2 tail = new Node2();

    public DList() {
        head.next = tail;
        tail.next = head;
    }

    // 将节点添加到头部
    public void addFirst(Node2 node2) {
        node2.next = head.next;
        head.next.pre = node2;
        head.next = node2;
        node2.pre = head;
        size++;
    }

    // 删除节点
    public void remove(Node2 node2) {
        node2.pre.next = node2.next;
        node2.next.pre = node2.pre;
        node2.next = null;
        node2.pre = null;
        size--;
    }

    // 将节点移动到头部
    public void moveFirst(Node2 node2) {
        remove(node2);
        addFirst(node2);
    }

    // 删尾节点
    public Node2 removeTail() {
        Node2 last = tail.pre;
        if (last != head) {
            remove(last);
            return last;
        }
        return null;
    }

    // 节点是否为头结点
    public boolean isFirst(Node2 node2) {
        return head.next == node2;
    }

    public int getSize() {
        return size;
    }
}